#include <vector>
#include <iostream>

using namespace std;

int staircase2(int height) {
  // 终结条件：递归不再继续的条件
  if (height == 0 || height == 1) {
    return 1;
  }

  // height
  // height - 1 height - 2
  // 递归公式
  return staircase2(height - 1) + staircase2(height - 2);
}

int staircase3(int height) {
  if (height == 0 || height == 1) {
    return 1;
  }
  
  if (height == 2) {
    return 2;
  }

  return staircase3(height - 1) + staircase3(height - 2) + staircase3(height - 3); // height >= 3
}

int staircase4(int height) {
  if (height == 0 || height == 1) {
    return 1;
  }
  
  if (height == 2) {
    return 2;
  }

  if (height == 3) {
    return 3;
  }

  return staircase4(height - 1) + staircase4(height - 2) + staircase4(height - 3) + staircase4(height - 4); // height >= 3
}

int staircase(int height, int max_step) {
  if (height == 0 || height == 1) {
    return 1;
  }

  return staircase(height - 1, max_step); + staircase(height - 2, max_step) + ... + staircase(height - max_step, max_step);
}

int main(int argc, char const *argv[])
{
  /* code */
  cout << staircase2(4) << endl;
  return 0;
}
